package 二叉树练习题;

import java.math.BigDecimal;

/**
 * 如何计算二叉树中两个结点的距离
 * <p>
 * 很多与二叉树相关的问题都可以通过对二叉树的遍历方法进行改装而求解。
 * 对本题而言，可以通过对二叉树的后序遍历进行改编而得到。
 * 具体思路为：查找结点node1 与结点node2的最近共同父结点可以转换为找到一个结点node，\
 * 使得node1与node2分别位于结点node的左子树或右子树中。
 * 例如，在上图中，结点1与结点5的最近共同父结点为结点3，
 * 因为结点1位于结点3的左子树上，而结点5位于结点3的右子树上
 */
public class H如何找出排序二叉树上任意两个结点的最近共同父结点 {

    public static BiTNode findParentNode(BiTNode root, BiTNode node1, BiTNode node2) {
        if (root == null || root == node1 || root == node2) {
            return root;
        }
        BiTNode lchild = findParentNode(root.lchild, node1, node2);
        BiTNode rchild = findParentNode(root.rchild, node1, node2);
        //root的左子树中没有节点node1和node2，那么一定在root的右子树上
        if (lchild == null) {
            return rchild;
        } else if (null == rchild) {
            return lchild;
        }
        //node1与node2分别位于root的左子树与右子树上，root就是他们最近的共同父节点
        else {
            return root;
        }
    }
}
